1. Field of the Invention
The present invention relates generally to the field of automated design techniques, and more particularly to methods and systems for identifying overconstraints during hierarchical compaction of integrated circuits.
2. Description of the Background Art
Many structures and systems are comprised of components whose interrelations are defined by a design rules. Such structures are often designed using automated design techniques employing symbolic representations of the structure and its elements. An example of such a structure is an integrated circuit.
The physical design of an integrated circuit is generally carried out in terms of the symbolic layout of the circuit, rather than the actual geometry of the masks and layers that comprise the chip. When creating mask works for integrated circuits, designers typically begin with a circuit schematic consisting of an interconnected network of logic or circuit elements. The designer generally has available a library of mask work patterns or "cells" which corresponds to the various circuit element used in the design. Creating a mask work then consists of transforming the circuit schematic by substituting various cells for the schematic circuit elements in such a way as to efficiently use the available mask area. The designer can thus work with transistors, wires, and other primitive components, and groups of these components using symbolic representations of these circuit elements. The symbolic layout provides a higher level of abstraction than the mask layout, and is therefore easier for the designer to manipulate. The use of a symbolic representation allows the designer to simulate and verify the logical operation of the circuit before actual fabrication.
A symbolic layout that contains only primitive symbols, i.e. transistors, wires, capacitors and other physical components, is termed a "leaf cell." The connections between cells are called "ports." Many layouts contain a large number of groups of components that are substantially identical. Such a group may be used to define a cell, and the description of the layout may then be simplified by treating each such group as an instance of this cell. The cell has its own symbol; for example it may be represented as a rectangle with various ports for connecting wires or for abutment with ports of adjacent cells that are represented similarly. The components of the overall layout then may consist of many cells, and the layout represents their relative placement and interconnection. Describing the layout in terms of cells rather than primitive symbols, further simplifies the designer's task.
Obviously this process of grouping elements and cells may be repeated, so that a symbolic layout can be treated as a hierarchical structure with multiple levels. Each level is a symbolic layout of various cells and primitive components. Each such cell is in turn a symbolic layout of subcells and primitive components, and this layout defines the next lower level of the hierarchy. Since there may be more than one type of cell at any given level, the next lower level may contain several different branches. The cells at the lowest level are leaf cells since they contain no subcells, but only primitive components. Cells at any other level are "hierarchy cells." The hierarchy can be visualized as an inverted "tree" with branches extending downward, and the lowest level depends on the branch in which it is located. In short, the leaf cells are at the ends of the branches, and the trunk of the tree represents the symbolic layout of the whole chip, which is often termed the "root cell." This hierarchical description is a natural and concise representation for large designs.
Once the symbolic layout is designed it is tested to verify its logical functioning. Any defective operation is remediated by design changes and re-verified. Once the design verification is completed, the layout is translated into a mask layout suitable for the actual fabrication of the chip. The translation maps the symbolic representation of the layout into a physical structure that implements the function of the layout. This translation requires additional technical information regarding the fabrication technology, which is stored in a "technology database" and used when the translation is carried out. For example, with semiconductor chips, the translation specifies the configuration of the physical structure of the circuit, identifying the precise placement and relationship of the various layers of semiconductors, insulators, substrates and the like. Using the translated layout, the masks for the circuit are prepared and the circuit is fabricated. The fabricated circuit is tested to verify its functional operation. Changes are made to the symbolic layout to remediate discrepancies between the intended and actual operation of the circuit, and a new mask work and chip is fabricated. This design and verify process is repeated until the chip operates as intended.
The task of integrated circuit design generally includes minimizing the geometrical size of the total structure. Minimization of size increases circuit performance by decreasing signal transmission distances. Minimization directly seeks to reduce the space between the physical elements comprising the circuit, such as traces, contacts between layers, and the like. The minimization process is subject to separation constraints that ensure that the technical design rules are followed and the integrity of the circuit is maintained.
Separation constraints generally describe the placement of circuit elements with respect to other circuit elements. There are three basic types of separation constraints:
1. Lower bound constraints: These are constraints that require, for two circuit elements A and B, that B is at least X units greater than A. Formally: A+X.ltoreq.B. PA1 2. Upper bound constraints: These are constraints that require, for two circuit elements A and B, that B is no more than X units greater than A. Formally: A+X.gtoreq.B. PA1 3. Equality constraints: These are constraints that require, for two circuit elements A and B, that A is X units from B. Formally: A+X=B. PA1 1. Constraints inherently present in the layout. These are constraints that enforce design rule correctness and preserve the underlying circuit integrity. PA1 2. Additional constraints required by the user, called user defined constraints. PA1 B is at least 5 units greater than A (A+5.ltoreq.B); PA1 C is at least 10 units greater than B (B+10.ltoreq.C); PA1 C is no more than 11 units greater than A (A+11.gtoreq.C). PA1 1. Intracell constraints that arise from constraints between shapes and devices within each of the leaf cells. PA1 2. Intercell constraints that arise from electrical and geometrical interactions between the leaf cells. PA1 3. Loop constraints that capture the geometric pattern of instances of cells in the layout.
The constraints that must be adhered to in minimizing a layout are of two types:
Inherent constraints, for example, require certain components of the circuit to be separated by a minimum distance, and the connections between different components must be maintained. User defined constraints may include requiring a cell to be of a minimum size to properly interface with other components.
The automated process of size minimization is known as compaction. A compactor is a computer program that operates on the input data of a symbolic layout, and produces a new symbolic layout. This new layout corresponds to a design of the minimum size circuit that preserves the integrity of the original circuit and complies with the design rule requirements. Compaction minimizes an objective function (generally representing the size of the layout in one dimension), while satisfying all constraints in the layout.
In some layouts, the defined constraints cannot all be satisfied simultaneously and there is no legal solution to the compaction problem. Such a system is said to be "overconstrained." For example, assume a circuit with elements A, B, and C, and the following constraints:
This system of separation constraints cannot be satisfied because the first two require that A is at least 15 units from C, but the last requires that A is no more than 11 units from C. Thus this system is overconstrained.
Current methods for identifying overconstraints are limited to leaf cells, and cannot identify overconstraints in hierarchical layouts. However, overconstraints are likely to be present in many large hierarchical layouts. It would be useful to have a compactor having an efficient method to identify and explain the overconstraints in hierarchical layouts and provide meaningful feedback to the user to eliminate them.
Because circuits can contain a complex hierarchy of cells, compaction of the physical structure of the circuit must maintain the logical and physical relationships between circuit elements in different levels of the hierarchy. It is necessary to both compact the organization of elements within a leaf cell and to maintain the port connectivity between abutting cells, termed "pitchmatching," while preserving the hierarchical structure. Given these requirements, the global compaction problem is formulated as a linear programming problem, which is solved by the "Revised Simplex Method."
Because the constraint system for hierarchical pitchmatching compaction is solved by linear programming, it is much more difficult to detect the source of the overconstraints. In contrast to leaf cell compaction, where the overconstraints are localized within a cell, in hierarchical compaction overconstraints usually occur due to the complex interaction of cells between and across the levels of hierarchy. Thus it is desirable to provide a method of displaying to the designer the relations between cells that lead to the overconstraint.
Further, as the number of variables and constraints that must be handled grows with the size of the hierarchy, the computation time increases rapidly with the hierarchy size. Hence, the complexity of the method is significant and the size of the layout that can be dealt with is limited. It is desirable then to provide a method that reduces the number of variables and constraints that must be solved to compact the layout, effectively increasing the size of layouts and complexity that can be efficiently designed.
In the discussion that follows the overconstraint system and method will be directed to the reduction of geometrical areas of an integrated circuit layout. It should be noted, however, that this method and system find useful application in the compaction of circuit board layouts as well.